﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#define N 3000005
int z[N] = { 0 };//0是质数 
__int64 phi[N] = { 0 };
__int64 sum[N] = { 0 };
int main()
{
    __int64 i, j;
    z[1] = 1;
    for (i = 2; i <= N; i++)
    {
        for (j = i * i; j <= N; j += i)
        {
            z[j] = 1;
        }
    }
    phi[1] = 1;
    for (i = 2; i <= N; i++)
    {
        if (z[i] == 1)
        {
            phi[i] = i;
        }
        else
        {
            phi[i] = i - 1;
        }
    }
    for (i = 2; i <= N; i++)
    {
        if (z[i] == 0)
        {
            for (j = 2; j * i <= N; j++)
            {
                phi[i * j] = phi[i * j] * phi[i] / i;
            }
        }
    }
    for (i = 1; i <= N; i++)
    {
        sum[i] = sum[i - 1] + phi[i];
    }
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%I64d\n", sum[b] - sum[a] + phi[a]);
    }
}

/*题目描述
对于整数n，定义ϕ(n)为小于或等于n，并与n互质的整数的个数，比如6,比它小的和它互质的数有1,5,所以ϕ(6)=2。 
如果n=p1^k1⋅p2^k2⋅…⋅pm^km，其中pi为不相同的素数。 那么ϕ(n)=n⋅(1−1/p1)⋅…⋅(1−1/pm)。

我们定义f(a,b)=∑bi=aϕ(i),请你写一个程序求f(a,b)。

输入
第一行是一个整数T(1≤T≤10000)，表示样例的个数。 每个样例是一行，为两个整数a,b(1≤a≤b≤3000000)。

输出
每行输出一个样例的结果。

样例输入
3  
1 6  
1 100  
1 1000000
*/